#include <iostream>
#include <stdlib.h>
#include <cstring>

using namespace std;

//======================== Definizione albero ==================================


/*
 *Struttura di un nodo: contiene un puntatore al padre (null se è radice)
 *un puntatore al figlio destro e uno al figlio sinistro, una stringa 
 *e un contatore delle occorrenze di quella stringa.
 */

typedef struct tree{
  struct tree * parent;
  char * string;
  int ric;
  struct tree *left;
  struct tree *right;
} tree;


//========================= Dichiarazione funzioni =============================

void previsit(tree *);
void invisit(tree *);
void postvisit(tree *);
void revvisit(tree *);
int strcmp(char *, char *);
void insert(tree * , char*);
tree * create(tree *, char*);


//============================= Sezione Main ===================================

int main(){
  char c='n';
  char * str;
  tree * tr = NULL;

  while (c != 'x'){

    switch (c){
    case 'n' :
      str = (char*) malloc(256 * sizeof(char));
      if (str == NULL) {
        cout<<"memoria esaurita"<<endl;
        return -1;
      }
      cout<<"dammi un valore"<<endl;
      cin>>str;
      if (tr == NULL) 
	tr = create(NULL, str);
      else{ 
	insert(tr, str);}
      break;
      
    case 'i' :
      invisit(tr);
      break;

    case 'p' :
      postvisit(tr);
      break;

    case 'e' :
      previsit(tr);
      break;

    case 'r':
      revvisit(tr);
      break;
      
    default:
      cout<<"Errore!"<<endl;
      break;
	}

    cout<<endl;
    cout<<"(N)uovo valore, (I)nvisit, (P)ostvisit, Pr(e)visit, (R)evvisit, E(x)it"<<endl;
    cin>>c;
  }
  
  return 0;
}


//====================== Dichiarazione Funzioni di Visita ======================

/*
 *Visita l'albero in preordine: prima il nodo più alto, poi il figlio destro, 
 *poi il figlio sinistro.
 *Il risultato è una stampa dall'alto in basso, da sinistra a destra dell'albero
 */
void previsit(tree * t){
  cout<<t->string<<" ";
  if (t->left != NULL ) previsit(t->left);
  if (t->right != NULL )previsit(t->right);
};


/*
 *Visita l'albero in ordine: prima il nodo più bassoa sinistra, poi il padre di
 *questo, poi il fratello, il nonno, lo zio...
 *In pratica restituisce una lista in ordine crescente dei valori.
 */
void invisit (tree * t){
  if (t->left != NULL ) invisit(t->left);
  cout<<t->string<<" ";
  if (t->right != NULL ) invisit(t->right);
}

/*
 *Visita l'albero in postordine: prima il nodo più in basso a destra, poi il padre, 
 *il fratello, il nonno, lo zio...
 *Restituisce una lista in ordine decrescente.
 */
void postvisit (tree * t){
  if (t->left != NULL ) postvisit(t->left);
  if (t->right != NULL )postvisit(t->right);
  cout<<t->string<<" ";
}


/*
 *Visita l'albero in ordine rovescio: parte dal nodo più in basso a destra e arriva
 *alla radice.
 *Restituisce un albero rovesciato.
 */

void revvisit(tree * t){
  if (t->right != NULL )revvisit(t->right);
  if (t->left != NULL ) revvisit(t->left);
  cout<<t->string<<" ";
}

/*
  String Compare
  Prende due stringhe e le confronta:
  se sono uguali restituisce 0
  se è maggiore la prima 1
  se è maggiore la seconda 2. 
*/

/*int strcmp(char *s1, char *s2){
  int i=0, cmp;
  bool stop=false;
  while (!stop){

    if (s1[i]>s2[i]) {
      cmp=1;
      stop=true;
    }
    
    if(s1[i]<s2[i]){
      cmp=2;
      stop=true;
    }
    
    if (s1[i]=='\0'){ //controllo fine primo file
      cmp=1;
      stop=true;
    }

    if (s2[i]=='\0'){ //controllo fine secondo file
      cmp=2;
      stop=true;
    }
    
    if(s1[i]==s2[i]=='\0') { //controllo fine contemporanea (stessa parola)
      cmp=0;
      stop=true;
    }
    
    i++;

  }

  return cmp;
}*/


//===========================Gestione dell'albero===============================


//Crea un nodo e lo collega all'albero (se ne esiste già uno) inizializzandolo

tree* create(tree * t, char * val){
  tree * n=new tree;
  n->parent=t;
  n->string=val;
  n->ric=1;
  n->left=NULL;
  n->right=NULL;
  cout<<"Inserito: "<<n->string<<endl;
  return n;
}


/*
 *Inserisce un valore nell'albero: compie una ricerca ricorsiva finchè non trova il 
 *valore o finchè non viene indirizzato ad una foglia vuota (puntatore null) e in
 *quel caso crea un nuovo nodo contente  quel valore.
 */

void insert (tree *t, char str[]){
  int cmp;

  cmp = strncmp(str, t->string, 256);
  if (cmp>0) cmp=1;
  if (cmp<0) cmp=2;
  
  switch (cmp){
  case 0 :
    cout<<"inc ";
    t->ric++;
    break;
  case 1:
    cout<<"right ";
    if (t->right == NULL) t->right=create(t, str);
    else insert(t->right, str);
    break;
  case 2:
    cout<<"left ";
    if (t->left == NULL) t->left=create(t, str);
    else insert(t->left, str);
    break;
  default :
    cout<<"Error! Insert value in tree failed"<<endl;

  }

}
